{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Double a Number Represented as a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: doubleIt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻倍以链表形式表示的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>非空</strong> 链表的头节点 <code>head</code> ，表示一个不含前导零的非负数整数。</p>\n",
    "\n",
    "<p>将链表 <strong>翻倍</strong> 后，返回头节点<em> </em><code>head</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/28/example.png\" style=\"width: 401px; height: 81px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,8,9]\n",
    "<strong>输出：</strong>[3,7,8]\n",
    "<strong>解释：</strong>上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/28/example2.png\" style=\"width: 401px; height: 81px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [9,9,9]\n",
    "<strong>输出：</strong>[1,9,9,8]\n",
    "<strong>解释：</strong>上图中给出的链表，表示数字 999 。返回的链表表示数字 999 * 2 = 1998 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><font face=\"monospace\"><code>0 &lt;= Node.val &lt;= 9</code></font></li>\n",
    "\t<li>生成的输入满足：链表表示一个不含前导零的数字，除了数字 <code>0</code> 本身。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [double-a-number-represented-as-a-linked-list](https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [double-a-number-represented-as-a-linked-list](https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,8,9]', '[9,9,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def helper(head):\n",
    "            if head is None:\n",
    "                return (0, None) # carry, head\n",
    "            carry, nextHead = helper(head.next)\n",
    "            head.val <<= 1\n",
    "            head.val += carry\n",
    "            newCarry = head.val // 10\n",
    "            head.val %= 10\n",
    "            head.next = nextHead\n",
    "            return (newCarry, head)\n",
    "        newCarry, newHead = helper(head)\n",
    "        if newCarry > 0:\n",
    "            return ListNode(newCarry, newHead)\n",
    "        else:\n",
    "            return newHead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = ListNode()\n",
    "        dum.next = head\n",
    "        if head.val > 4:\n",
    "            node = ListNode(1)\n",
    "            node.next = head\n",
    "            dum.next = node \n",
    "        while head:\n",
    "            val = head.val * 2\n",
    "            if head.next and head.next.val > 4:\n",
    "                val += 1\n",
    "            head.val = val % 10\n",
    "            head = head.next\n",
    "       \n",
    "        return dum.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head.val > 4:\n",
    "            head = ListNode(0,head)\n",
    "        cur = head\n",
    "        while cur :\n",
    "            cur.val = cur.val*2%10\n",
    "            if cur.next and cur.next.val >4:\n",
    "                cur.val += 1\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        if head.val > 4:\r\n",
    "            head = ListNode(next=head)\r\n",
    "        cur = head\r\n",
    "        while cur:\r\n",
    "            cur.val = cur.val * 2 % 10\r\n",
    "            if cur.next and cur.next.val > 4:\r\n",
    "                cur.val += 1\r\n",
    "            cur = cur.next\r\n",
    "        return head\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p=head\n",
    "        value_list=[]\n",
    "        if head.val==0:\n",
    "            return head\n",
    "        def str2int(s):\n",
    "            ans=0\n",
    "            t=1\n",
    "            for ch in s[::-1]:\n",
    "                ans+=int(ch)*t\n",
    "                t*=10\n",
    "            return ans\n",
    "        def int2str(num):\n",
    "            s=''\n",
    "            while num:\n",
    "                s=str(num%10)+s\n",
    "                num//=10\n",
    "            return s\n",
    "        while p:\n",
    "            value_list.append(str(p.val))\n",
    "            p=p.next\n",
    "        value=''.join(value_list)\n",
    "        if str2int(value)<<1 >= 10**(len(value)):\n",
    "            new_ListNode=ListNode()\n",
    "            new_ListNode.next=head\n",
    "            value=int2str(str2int(value)<<1)\n",
    "            head=new_ListNode\n",
    "            i=0\n",
    "            while new_ListNode:\n",
    "                new_ListNode.val=int(value[i])\n",
    "                i+=1\n",
    "                new_ListNode=new_ListNode.next\n",
    "            return head\n",
    "        else:\n",
    "            value=int2str(str2int(value)*2)\n",
    "            p=head\n",
    "            i=0\n",
    "            while p:\n",
    "                p.val=int(value[i])\n",
    "                i+=1\n",
    "                p=p.next\n",
    "            return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def flip(self, head):\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = self.flip(head)\n",
    "        cur = head\n",
    "        carry = 0\n",
    "        k = 2\n",
    "        res = None\n",
    "        while cur or carry:\n",
    "            if cur:\n",
    "                carry += cur.val * k\n",
    "                cur = cur.next\n",
    "            newnode = ListNode(val=carry % 10, next=res)\n",
    "            res = newnode\n",
    "            carry //= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num = 0\n",
    "        while head:\n",
    "            num *= 10\n",
    "            num += head.val\n",
    "            head = head.next\n",
    "        doubleNum = num * 2\n",
    "\n",
    "        if doubleNum == 0:\n",
    "            temp = ListNode()\n",
    "            temp.val = 0\n",
    "            temp.next = None\n",
    "            return temp\n",
    "        \n",
    "        last = None\n",
    "        while doubleNum:\n",
    "            temp = ListNode()\n",
    "            temp.val = doubleNum % 10\n",
    "            temp.next = last\n",
    "            last = temp\n",
    "            doubleNum //= 10\n",
    "        \n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        root_val=[]\n",
    "        cur=head\n",
    "        while cur:\n",
    "            root_val.append(cur.val)\n",
    "            cur=cur.next\n",
    "        n=len(root_val)\n",
    "        new_root_val=[0 if i==0 else root_val[i-1]*2 for i in range(n+1)]\n",
    "        del root_val\n",
    "        print(new_root_val)\n",
    "        for i in range(n,-1,-1):\n",
    "            new_root_val[i],new_root_val[i-1]=new_root_val[i]%10,new_root_val[i]//10+new_root_val[i-1]\n",
    "        dummy_head=ListNode(0)\n",
    "        cur=dummy_head\n",
    "        for i in range(n+1):\n",
    "            if i==0:\n",
    "                if new_root_val[i]==0:\n",
    "                    pass\n",
    "                else:\n",
    "                    node=ListNode(new_root_val[i])\n",
    "                    cur.next=node\n",
    "                    cur=cur.next\n",
    "            else:\n",
    "                node=ListNode(new_root_val[i])\n",
    "                cur.next=node\n",
    "                cur=cur.next\n",
    "        del new_root_val\n",
    "        return dummy_head.next\n",
    "                    \n",
    "                    \n",
    "                \n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "sys.set_int_max_str_digits(12000)\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = []\n",
    "        p = head\n",
    "        while p:\n",
    "            l.append(str(p.val))\n",
    "            p = p.next\n",
    "        s = int(''.join(l)) * 2\n",
    "        s = str(s)\n",
    "        res = ListNode()\n",
    "        p = res\n",
    "        for c in s:\n",
    "            p.next = ListNode(int(c))\n",
    "            p = p.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(1<<20)\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num_list = []\n",
    "        while head.next != None:\n",
    "            num_list.append(str(head.val))\n",
    "            head = head.next\n",
    "        num_list.append(str(head.val))\n",
    "        sum = \"\".join(num_list)\n",
    "        # sum = 0\n",
    "        # for index, num in enumerate(num_list[::-1]):\n",
    "        #     sum += num * 10**index\n",
    "        # s=__Serializer__()._serialize(head,'ListNode')\n",
    "        # sum=\"\".join(filter(str.isdigit,s))\n",
    "        res = list(map(int, list(str(int(sum)*2))))\n",
    "        # head = ListNode(res[0])\n",
    "        # fin = head\n",
    "        # for i in res[1:]:\n",
    "        #     head.next = ListNode(i)\n",
    "        #     head = head.next\n",
    "        # return __Deserializer__()._deserialize(\"\".join(list(map(int, list(str(sum*2))))),'ListNode')\n",
    "        return __Deserializer__()._deserialize(str(res),'ListNode')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def multiply(self, num1: str, num2: str) -> str:\n",
    "        if num1 == \"0\" or num2 == \"0\":\n",
    "            return \"0\"\n",
    "        \n",
    "        m, n = len(num1), len(num2)\n",
    "        ansArr = [0] * (m + n)\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            x = int(num1[i])\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                ansArr[i + j + 1] += x * int(num2[j])\n",
    "        \n",
    "        for i in range(m + n - 1, 0, -1):\n",
    "            ansArr[i - 1] += ansArr[i] // 10\n",
    "            ansArr[i] %= 10\n",
    "        \n",
    "        index = 1 if ansArr[0] == 0 else 0\n",
    "        ans = \"\".join(str(x) for x in ansArr[index:])\n",
    "        return ans\n",
    "\n",
    "    \n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return 0\n",
    "        temp = head\n",
    "        num = []\n",
    "        while temp:\n",
    "            num.append(str(temp.val))\n",
    "            temp = temp.next\n",
    "        res = self.multiply(\"\".join(num), \"2\")\n",
    "        dummy = ListNode(-1, None)\n",
    "        ptr = dummy\n",
    "        for temp in res:\n",
    "            ptr.next = ListNode(int(temp), None)\n",
    "            ptr = ptr.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverseList(head: ListNode) -> ListNode:\n",
    "            result = ListNode()\n",
    "            tmp = head\n",
    "            result_tmp = result\n",
    "            while head:\n",
    "                result.val = head.val\n",
    "                result_tmp = ListNode(0, result)\n",
    "                result = result_tmp\n",
    "                head = head.next\n",
    "            return result_tmp.next\n",
    "    \n",
    "        head = reverseList(head)\n",
    "        carry = 0\n",
    "        tmp = head\n",
    "        while tmp:\n",
    "            v = tmp.val * 2 + carry\n",
    "            carry, tmp.val = divmod(v, 10)\n",
    "            tmp = tmp.next\n",
    "\n",
    "        head = reverseList(head)\n",
    "        return ListNode(carry, head) if carry else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        result = ListNode()\n",
    "        tmp = head\n",
    "        result_tmp = result\n",
    "        while head:\n",
    "            result.val = head.val\n",
    "            result_tmp = ListNode(0, result)\n",
    "            result = result_tmp\n",
    "            head = head.next\n",
    "        return result_tmp.next\n",
    "    \n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = self.reverseList(head)\n",
    "        carry = 0\n",
    "        tmp = head\n",
    "        while tmp:\n",
    "            v = tmp.val * 2 + carry\n",
    "            carry, tmp.val = divmod(v, 10)\n",
    "            tmp = tmp.next\n",
    "        head = self.reverseList(head)\n",
    "        return ListNode(carry, head) if carry else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        last = self.get_last(head)\n",
    "\n",
    "        mark = 0\n",
    "        while last != None :\n",
    "            v = (last.val * 2) + mark\n",
    "\n",
    "            if v >= 10 :\n",
    "                mark = v // 10\n",
    "                v = v % 10\n",
    "\n",
    "                pass\n",
    "            else:\n",
    "                mark = 0\n",
    "                pass\n",
    "            last.val = v\n",
    "\n",
    "            last = last.prev\n",
    "            pass\n",
    "        if mark > 0 :\n",
    "            redu = ListNode(mark)\n",
    "            redu.next = head\n",
    "            return redu\n",
    "            pass\n",
    "        return head\n",
    "        pass\n",
    "\n",
    "    def get_last(self, head) :\n",
    "        if head == None :\n",
    "            return head\n",
    "        head.prev = None\n",
    "        p1,p2 = head,head.next\n",
    "        while p2 != None :\n",
    "            p2.prev = p1\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "            pass\n",
    "        return p1\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head.pre = None\n",
    "        if head.val == 0:\n",
    "            return head\n",
    "        now = head\n",
    "        while now.next:\n",
    "            now.next.pre = now\n",
    "            now = now.next\n",
    "        ten = 0\n",
    "        while True:\n",
    "            k = now.val * 2 + ten\n",
    "            if k > 9:\n",
    "                ten = 1\n",
    "                now.val = k - 10\n",
    "            else:\n",
    "                ten = 0\n",
    "                now.val = k\n",
    "            now = now.pre\n",
    "            if now is None:\n",
    "                break\n",
    "        if ten:\n",
    "            return ListNode(1, head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        carry_bit = backtracking(head)\n",
    "        if carry_bit:\n",
    "            new_node = ListNode(1, head)\n",
    "            head = new_node\n",
    "        return head\n",
    "\n",
    "def backtracking(head):\n",
    "    if head == None:\n",
    "        return 0 \n",
    "    else:\n",
    "        carry_bit = backtracking(head.next)\n",
    "        val = (2 * head.val + carry_bit) % 10\n",
    "        carry_bit = (2 * head.val + carry_bit) // 10\n",
    "        head.val = val \n",
    "        return carry_bit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return 0\n",
    "            val = head.val * 2 + dfs(head.next)\n",
    "            head.val = val % 10\n",
    "            return val // 10\n",
    "\n",
    "        return ListNode(1, head) if dfs(head) else head \n",
    "'''\n",
    "作者：newhar\n",
    "链接：https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/solutions/2385928/lian-biao-dao-xu-chu-li-ji-qiao-di-gui-b-0n1z/\n",
    "'''"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
